package week9.Chapter11_二叉查找树.jsjf.PP11_8;

import week6.Chapter6_列表.jsjf.ArrayUnorderedList;
import week6.Chapter6_列表.jsjf.UnorderedListADT;
import week8.Chapter10_树.jsjf.exceptions.ElementNotFoundException;
import week8.Chapter10_树.jsjf.exceptions.EmptyCollectionException;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack;

/**
 * LinkedBinaryTree implements the BinaryTreeADT interface
 *
 * @author Lewis and Chase
 * @version 4.0
 */
public class LinkedBinaryTree<T extends Comparable<T>> implements BinaryTreeADT<T>, Iterable<T>
{
    protected BinaryTreeNode<T> root;
    protected int modCount;
    protected int count;  //  记录树中元素个数

    /**
     * Creates an empty binary tree.
     */
    public LinkedBinaryTree()
    {
        root = null;
    }

    /**
     * Creates a binary tree with the specified element as its root.
     *
     * @param element the element that will become the root of the binary tree
     */
    public LinkedBinaryTree(T element)
    {
        root = new BinaryTreeNode<T>(element);
    }

    /**
     * Creates a binary tree with the specified element as its root and the
     * given trees as its left child and right child
     *
     * @param element the element that will become the root of the binary tree
     * @param left the left subtree of this tree
     * @param right the right subtree of this tree
     */
    public LinkedBinaryTree(T element, LinkedBinaryTree<T> left,
                            LinkedBinaryTree<T> right)
    {
        root = new BinaryTreeNode<T>(element);
        root.setLeft(left.root);
        root.setRight(right.root);
    }

    /**
     * Returns a reference to the element at the root
     *
     * @return a reference to the specified target
     * @throws EmptyCollectionException if the tree is empty
     */
    @Override
    public T getRootElement() throws EmptyCollectionException
    {
        // To be completed as a Programming seatwork
        if (isEmpty()){
            throw new EmptyCollectionException("LinkedBinaryTree");
        }
        return root.element;
    }

    /**
     * Returns a reference to the node at the root
     *
     * @return a reference to the specified node
     * @throws EmptyCollectionException if the tree is empty
     */
    protected BinaryTreeNode<T> getRootNode() throws EmptyCollectionException
    {
        // To be completed as a Programming seatwork
        if (isEmpty()){
            throw new EmptyCollectionException("LinkedBinaryTree");
        }
        return root;
    }
    // 获取根结点
    public BinaryTreeNode<T> getRoot() {
        return root;
    }

    /**
     * Returns the left subtree of the root of this tree.
     *
     * @return a link to the left subtree fo the tree
     */
    public LinkedBinaryTree<T> getLeft()
    {
        // To be completed as a Programming seatwork
        LinkedBinaryTree result = new LinkedBinaryTree();
        result.root = root.getLeft();
        return result;

    }

    /**
     * Returns the right subtree of the root of this tree.
     *
     * @return a link to the right subtree of the tree
     */
    public LinkedBinaryTree<T> getRight()
    {
        // To be completed as a Programming seatwork
        LinkedBinaryTree result = new LinkedBinaryTree();
        result.root = root.getRight();
        return result;

    }

    /**
     * Returns true if this binary tree is empty and false otherwise.
     *
     * @return true if this binary tree is empty, false otherwise
     */
    @Override
    public boolean isEmpty()
    {
        if (root != null){
            return false;
        }
        else {
            return true;
        }
    }

    /**
     * Returns the integer size of this tree.
     *
     * @return the integer size of the tree
     */
    @Override
    public int size()
    {
        // To be completed as a Programming seatwork
       if (root!=null){
           return root.numChildren() + 1;
       }
       else {
           return 0;
       }
//        return count;
    }

    /**
     * Returns the height of this tree.
     *
     * @return the height of the tree
     */
     public int getHeight()
    {
        // To be completed as a Programming seatwork
//        int front = -1, rear = -1;
//        int last = 0, level = 0;
//        BinaryTreeNode[] queue = new BinaryTreeNode[100000];
//        if (root == null) {
//            return 0;
//        }
//        queue[++rear]= root;
//        BinaryTreeNode current;
//        while(front<rear){
//            current=queue[++front];
//            if(current.left!=null){
//                queue[++rear]=current.left;
//            }
//            if(current.right!=null){
//                queue[++rear]=current.right;
//            }
//            if(front==last){
//                level++;
//                last=rear;
//            }
//        }
//        return level;
        return height(root);
    }

    /**
     * Returns the height of the specified node.
     *
     * @param node the node from which to calculate the height
     * @return the height of the tree
     */
    private int height(BinaryTreeNode<T> node)
    {
        // To be completed as a Programming seatwork
        if (node==null){
            return 0;
        }
        else {
            int left = height(node.left);
            int right = height(node.right);
            return (left > right) ? (left + 1) : (right + 1);
        }
//        if (node==null){
//            return 0;
//        }
//        else {
//            int left = height(root.left);
//            int right = height(root.right);
//            if (left > right){
//                return left + 1;
//            }
//            else {
//                return right + 1;
//            }
//        }
    }

    /**
     * Returns true if this tree contains an element that matches the
     * specified target element and false otherwise.
     *
     * @param targetElement the element being sought in this tree
     * @return true if the element in is this tree, false otherwise
     */
    @Override
    public boolean contains(T targetElement)
    {
        // To be completed as a Programming seatwork
        T temp;
        boolean found = false;

        try {
            temp = find(targetElement);
            found = true;
        }
        catch (Exception ElementNotFoundExecption){
            found = false;
        }
        return found;
    }

    /**
     * Returns a reference to the specified target element if it is
     * found in this binary tree.  Throws a ElementNotFoundException if
     * the specified target element is not found in the binary tree.
     *
     * @param targetElement the element being sought in this tree
     * @return a reference to the specified target
     * @throws ElementNotFoundException if the element is not in the tree
     */
    @Override
    public T find(T targetElement) throws ElementNotFoundException
    {
        BinaryTreeNode<T> current = findNode(targetElement, root);

        if (current == null) {
            throw new ElementNotFoundException("LinkedBinaryTree");
        }

        return (current.getElement());
    }

    /**
     * Returns a reference to the specified target element if it is
     * found in this binary tree.
     *
     * @param targetElement the element being sought in this tree
     * @param next the element to begin searching from
     */
    private BinaryTreeNode<T> findNode(T targetElement,
                                       BinaryTreeNode<T> next)
    {
        if (next == null) {
            return null;
        }

        if (next.getElement().equals(targetElement)) {
            return next;
        }

        BinaryTreeNode<T> temp = findNode(targetElement, next.getLeft());

        if (temp == null) {
            temp = findNode(targetElement, next.getRight());
        }

        return temp;
    }

    //  删除左子树
    public LinkedBinaryTree removeLeftsubtree(){
        LinkedBinaryTree Leftsubtree = new LinkedBinaryTree();
        Leftsubtree.root = root;
        root.left = null;
        return Leftsubtree;
    }
    //  删除右子树
    public LinkedBinaryTree removeRightsubtree(){
        LinkedBinaryTree Rightsubtree = new LinkedBinaryTree();
        Rightsubtree.root = root;
        root.right = null;
        return Rightsubtree;
    }
    //     删除指定结点的左子树
    public LinkedBinaryTree removeNodeLeftsubtree(T Element){
        BinaryTreeNode node = new BinaryTreeNode(Element);
        LinkedBinaryTree linkedBinaryTree = new LinkedBinaryTree();
        linkedBinaryTree.root = root;
        if (root==null){
            return linkedBinaryTree;
        }
        else {
            if (root != null && root.left == null && root.right == null) {
                linkedBinaryTree.root = root;
                return linkedBinaryTree;
            }
            node = findNode(Element,root);
            node.left = null;
            linkedBinaryTree.root = root;
            return linkedBinaryTree;
        }

//            //递归删除二叉树中以x为根的子树，（flag为标志）
////        LinkedBinaryTree linkedBinaryTree = new LinkedBinaryTree();
////        linkedBinaryTree.root = root;
//            if(current == null)
//            {
//                return 0 ;
//            }
//            else
//            {
//
//                if(current.element == Element)    //如果当前节点的值为x，则更改标志位，在下面将向递归子函数中传递flag值
//                {
//                    flag = 1;
//                }
//                int lefttree = removeNodeLeftsubtree(current, Element,flag);  //递归左子树，lef_ret为从左子树中返回的信息
//                int righttree = removeNodeLeftsubtree(current,Element,flag);  //递归右子树，rig_ret为从右子树中返回的信息
//                if(1 == flag)       //如果标志为1，说明其祖父结点中有x，也就是说当前结点需要删除
//                {
//                    if(current.element == Element)    //如果是x结点，则需要向上层结点传递信息，以便其父节点将对应的指针域赋空
//                    {
//                        return 1;
//                    }
//                    current = null;
//                }
//                else
//                {
//                    if(1 == lefttree)    //从子结点接受收的信息，即如果其子结点为x，需要将其指针域赋空
//                    {
//                       current.left = null;
//                    }
//                    if(1 == righttree )   //从子结点接受收的信息，即如果其子结点为x，需要将其指针域赋空
//                    {
//                        current.right = null;
//                    }
//                }
//            }
//            return  0;
    }
    // 删除所有元素
    public LinkedBinaryTree removeAllElements(){
        LinkedBinaryTree Tree = new LinkedBinaryTree();
        Tree.root = null;
        return Tree;
    }
    // 插入元素
    public void add(T Element){
//                String error = null;
        BinaryTreeNode node = new BinaryTreeNode(Element);
        if (root == null) {
            root = node;
            count++;
            root.left = null;
            root.right = null;
        } else {
            BinaryTreeNode current = root;
            BinaryTreeNode parent = null;
            while (true) {
                if (Element.compareTo((T) current.element)<0) {
                    parent = current;
                    current = current.left;
                    if (current == null) {
                        parent.left = node;
                        count++;
                        break;
                    }
                } else if (Element.compareTo((T) current.element)>0) {
                    parent = current;
                    current = current.right;
                    if (current == null) {
                        parent.right = node;
                        count++;
                        break;
                    }
                }
//                        else {
//                            error = "having same value in binary tree";
//                        }
            } // end of while
        }
    }

    // 判断某一结点是叶子结点还是内部结点
    protected String Judging_results;
    public boolean Judgenode(T Element) {
        BinaryTreeNode<T> node = new BinaryTreeNode<T>(Element);
        if (root == null){
            Judging_results = "It's not a leaf or an internal node .";
            return false;
        }
        else {
            if (root != null&&root.left==null&&root.right==null){
                Judging_results = "Both leaves and internal nodes .";
            }
            node = findNode(Element,root);
            if (node.left!=null||node.right!=null){
                Judging_results = "internal nodes .";
                return true;
            }
            else {
                Judging_results = "leaf nodes . ";
                return false;
            }
        }
    }

    //  计算树的叶子结点个数
    public int CountLeaf(BinaryTreeNode T , int countLeaf){
        if (T == null){
            countLeaf = 0 ;
        }
        if (T.left==null&&T.left==null){
            System.out.println("叶子结点 ： " + T.getElement());
            countLeaf = 1;
        }
        else {
            return CountLeaf(T.getLeft(),countLeaf) + CountLeaf(T.getRight(),countLeaf);
        }
        return countLeaf;
    }

    // 递归实现层级遍历
    public void LevelOrder_recursion(BinaryTreeNode<T> node){
        if (node==null){
            System.out.println("This node is null");
        }
        int height = height(root);
        for (int i = 1; i <= height ; i++){
            Level_traversal(node,i);
        }
    }
    int num = 0;
    protected void Level_traversal(BinaryTreeNode<T> node , int Level ){
        if (node == null || Level<1){
            return;
        }
        else {
            if (Level==1){
                num++;
                System.out.println("第" + num + "个结点 ： " + node.getElement());
                return;
            }
        }

        Level_traversal(node.left,Level-1);
        Level_traversal(node.right,Level-1);
    }
    // 非递归实现层级遍历
    public void LevelOrder_norecursion(){
        ArrayUnorderedList<BinaryTreeNode<T>> templist = new ArrayUnorderedList<BinaryTreeNode<T>>();
        BinaryTreeNode current = root;
        templist.addToFront(root);
        num = 0;
        while (!templist.isEmpty()){
            num++;
            current = templist.first();
            System.out.println("第" + num + "个结点 ： " + templist.first().getElement());
            if (current.getLeft()!=null||current.getRight()!=null){
                if (current.getLeft()!=null){
                    templist.addToRear(current.getLeft());
                }
                if (current.getRight()!=null){
                    templist.addToRear(current.getRight());
                }

            }
            templist.removeFirst();
        }
    }



    /**
     * Returns a string representation of this binary tree showing
     * the nodes in an inorder fashion.
     *
     * @return a string representation of this binary tree
     */
    @Override
    public String toString()
    {
        // To be completed as a Programming seatwork
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        preOrder(root,tempList);

        return tempList.toString();
    }
    public String printTree()
    {
        UnorderedListADT<BinaryTreeNode<T>> nodes =
                new ArrayUnorderedList<BinaryTreeNode<T>>();
        UnorderedListADT<Integer> levelList =
                new ArrayUnorderedList<Integer>();
        BinaryTreeNode<T> current;
        String result = "";
        int printDepth = this.getHeight();
        int possibleNodes = (int)Math.pow(2, printDepth + 1);
        int countNodes = 0;

        nodes.addToRear(root);
        Integer currentLevel = 0;
        Integer previousLevel = -1;
        levelList.addToRear(currentLevel);

        while (countNodes < possibleNodes)
        {
            countNodes = countNodes + 1;
            current = nodes.removeFirst();
            currentLevel = levelList.removeFirst();
            if (currentLevel > previousLevel)
            {
                result = result + "\n\n";
                previousLevel = currentLevel;
                for (int j = 0; j < ((Math.pow(2, (printDepth - currentLevel))) - 1); j++) {
                    result = result + " ";
                }
            }
            else
            {
                for (int i = 0; i < ((Math.pow(2, (printDepth - currentLevel + 1)) - 1)) ; i++)
                {
                    result = result + " ";
                }
            }
            if (current != null)
            {
                result = result + (current.getElement()).toString();
                nodes.addToRear(current.getLeft());
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(current.getRight());
                levelList.addToRear(currentLevel + 1);
            }
            else {
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                result = result + " ";
            }

        }

        return result;
    }

    public void showTree(){
        Stack globalStack=new Stack();
        globalStack.push(root);
        // int nBlank=32;
        int nBlank=64;
        boolean isRowEmpty=false;
        String dot="............................";
        System.out.println(dot+dot+dot);
        while (isRowEmpty==false){
            Stack localStack=new Stack();
            isRowEmpty=true;
            for (int j=0;j<nBlank;j++)//{
            {

                System.out.print("-");
            }
            while (globalStack.isEmpty()==false){
                //里面的while循环用于查看全局的栈是否为空
                BinaryTreeNode temp=(BinaryTreeNode) globalStack.pop();
                if (temp!=null){
                    System.out.print(temp.element);
                    localStack.push(temp.left);
                    localStack.push(temp.right);
                    //如果当前的节点下面还有子节点，则必须要进行下一层的循环
                    if (temp.left!=null||temp.right!=null){
                        isRowEmpty=false;
                    }
                }else {
                    //如果全局的栈则不为空
                    System.out.print("#!");
                    localStack.push(null);
                    localStack.push(null);

                }
                //打印一些空格
                for (int j=0;j<nBlank*2-2;j++){
                    //System.out.print("&");
                    System.out.print("-");
                }
            }//while end
            System.out.println();
            nBlank/=2;
            //这个while循环用来判断，local栈是否为空,不为空的话，则取出来放入全局栈中
            while (localStack.isEmpty()==false){
                globalStack.push(localStack.pop());
            }
        }//大while循环结束之后，输出换行
        System.out.println(dot+dot+dot);
    }

    /**
     * Returns an iterator over the elements in this tree using the
     * iteratorInOrder method
     *
     * @return an in order iterator over this binary tree
     */
    @Override
    public Iterator<T> iterator()
    {
        return iteratorInOrder();
    }

    /**
     * Performs an inorder traversal on this binary tree by calling an
     * overloaded, recursive inorder method that starts with
     * the root.
     *
     * @return an in order iterator over this binary tree
     */
    @Override
    public Iterator<T> iteratorInOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        inOrder(root, tempList);

        return new TreeIterator(tempList.iterator());
    }

    /**
     * Performs a recursive inorder traversal.
     *
     * @param node the node to be used as the root for this traversal
     * @param tempList the temporary list for use in this traversal
     */
    protected void inOrder(BinaryTreeNode<T> node,
                           ArrayUnorderedList<T> tempList)
    {
        if (node != null)
        {
            inOrder(node.getLeft(), tempList);
            tempList.addToRear(node.getElement());
            inOrder(node.getRight(), tempList);
        }
    }

    /**
     * Performs an preorder traversal on this binary tree by calling
     * an overloaded, recursive preorder method that starts with
     * the root.
     *
     * @return a pre order iterator over this tree
     */
    @Override
    public Iterator<T> iteratorPreOrder()
    {
        // To be completed as a Programming seatwork
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        preOrder (root, tempList);

        return tempList.iterator();

    }

    /**
     * Performs a recursive preorder traversal.
     *
     * @param node the node to be used as the root for this traversal
     * @param tempList the temporary list for use in this traversal
     */
    protected void preOrder(BinaryTreeNode<T> node,
                            ArrayUnorderedList<T> tempList)
    {
        // To be completed as a Programming seatwork
        if (node!=null){
            tempList.addToRear(node.element);
            preOrder(node.left,tempList);
            preOrder(node.right,tempList);
        }

    }

    /**
     * Performs an postorder traversal on this binary tree by calling
     * an overloaded, recursive postorder method that starts
     * with the root.
     *
     * @return a post order iterator over this tree
     */
    @Override
    public Iterator<T> iteratorPostOrder()
    {
        // To be completed as a Programming seatwork
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        postOrder (root, tempList);

        return tempList.iterator();
    }

    /**
     * Performs a recursive postorder traversal.
     *
     * @param node the node to be used as the root for this traversal
     * @param tempList the temporary list for use in this traversal
     */
    protected void postOrder(BinaryTreeNode<T> node,
                             ArrayUnorderedList<T> tempList)
    {
        // To be completed as a Programming seatwork
        if (node != null)
        {
            postOrder(node.getLeft(), tempList);
            postOrder(node.getRight(), tempList);
            tempList.addToRear(node.getElement());
        }
    }

    /**
     * Performs a levelorder traversal on this binary tree, using a
     * templist.
     *
     * @return a levelorder iterator over this binary tree
     */
    @Override
    public Iterator<T> iteratorLevelOrder()
    {
        ArrayUnorderedList<BinaryTreeNode<T>> nodes =
                              new ArrayUnorderedList<BinaryTreeNode<T>>();
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        BinaryTreeNode<T> current;

        nodes.addToRear(root);

        while (!nodes.isEmpty())
        {
            current = nodes.removeFirst();

            if (current != null)
            {
                tempList.addToRear(current.getElement());
                if (current.getLeft() != null) {
                    nodes.addToRear(current.getLeft());
                }
                if (current.getRight() != null) {
                    nodes.addToRear(current.getRight());
                }
            }
            else {
                tempList.addToRear(null);
            }
        }

        return new TreeIterator(tempList.iterator());
    }



    /**
     * Inner class to represent an iterator over the elements of this tree
     */
    private class TreeIterator implements Iterator<T>
    {
        private int expectedModCount;
        private Iterator<T> iter;

        /**
         * Sets up this iterator using the specified iterator.
         *
         * @param iter the list iterator created by a tree traversal
         */
        public TreeIterator(Iterator<T> iter)
        {
            this.iter = iter;
            expectedModCount = modCount;
        }

        /**
         * Returns true if this iterator has at least one more element
         * to deliver in the iteration.
         *
         * @return  true if this iterator has at least one more element to deliver
         *          in the iteration
         * @throws  ConcurrentModificationException if the collection has changed
         *          while the iterator is in use
         */
        @Override
        public boolean hasNext() throws ConcurrentModificationException
        {
            if (!(modCount == expectedModCount)) {
                throw new ConcurrentModificationException();
            }

            return (iter.hasNext());
        }

        /**
         * Returns the next element in the iteration. If there are no
         * more elements in this iteration, a NoSuchElementException is
         * thrown.
         *
         * @return the next element in the iteration
         * @throws NoSuchElementException if the iterator is empty
         */
        @Override
        public T next() throws NoSuchElementException
        {
            if (hasNext()) {
                return (iter.next());
            } else {
                throw new NoSuchElementException();
            }
        }

        /**
         * The remove operation is not supported.
         *
         * @throws UnsupportedOperationException if the remove operation is called
         */
        @Override
        public void remove()
        {
            throw new UnsupportedOperationException();
        }
        }
//    @Override
//    public int compareTo(T element) {
//        BinaryTreeNode binaryTreeNode;
//        if ((int)binaryTreeNode.element < (int)element){
//            return -1;
//        }
//        else
//        if ((int)binaryTreeNode.element > (int)element){
//            return 1;
//        }
//        else {return 0;}
//    }
//    }

    private static int Depth(BinaryTreeNode binaryTreeNode){
        if (binaryTreeNode==null){
            return 0;
        }
        int LeftLength = Depth(binaryTreeNode.left);
        int RightLength = Depth(binaryTreeNode.right);
        return (LeftLength > RightLength ? LeftLength : RightLength) + 1;
    }
    private static boolean isBalanceTree(BinaryTreeNode binaryTreeNode){
        if (binaryTreeNode==null){
            return true;
        }
        int LeftLength = Depth(binaryTreeNode.left);
        int RightLength = Depth(binaryTreeNode.right);
        int distance = (LeftLength > RightLength) ?( LeftLength - RightLength) : (RightLength - LeftLength);
        if (distance > 1){
            return false;
        }
        else {
            return isBalanceTree(binaryTreeNode.left)&&isBalanceTree(binaryTreeNode.right);
        }
    }
    private BinaryTreeNode singleLeftRotation(BinaryTreeNode tree) {
        //将被破坏节点的左子节点提升为根节点
        BinaryTreeNode root = tree.left;
        // root的右子树变为tree的左子树
        tree.left = root.right;
        // tree变为root的左子树
        root.right = tree;

        tree.height = Math.max(Depth(tree.left),Depth(tree.right)) + 1;
        root.height = Math.max(Depth(root.left),tree.height) + 1;
//        //如果新根节点的右边不为空，把它放进被破坏节点的左边
//        tree.left = root.right == null ? null : root.right;
//
//        //被破坏节点放进新根节点的右边
//        root.right = tree;
//
        return root;
    }
    private BinaryTreeNode singleRightRotation(BinaryTreeNode tree) {
        //将被破坏节点的右子节点提升为根节点
        BinaryTreeNode root = tree.right;
        tree.right = root.left;
        root.right = tree;
        tree.height = Math.max(Depth(tree.left),Depth(tree.right)) + 1;
        root.height = Math.max(Depth(root.left),tree.height) + 1;

//        //如果新根节点的左边不为空，转移到被破坏节点的右边
//        tree.right = root.left == null ? null : root.left;
//
//        //被破坏节点放进新根节点的左边
//        root.left = tree;
        return root;
    }
    private BinaryTreeNode doubleLeftRightRotation(BinaryTreeNode tree) {
        tree.left = singleRightRotation(tree.left);
        return singleLeftRotation(tree);
    }
    private BinaryTreeNode doubleRightLeftRotation(BinaryTreeNode tree) {
        tree.right = singleLeftRotation(tree.right);
        return singleRightRotation(tree);
    }
    public void insert(T element){
//        BinaryTreeNode binaryTreeNode = new BinaryTreeNode(element);
        root = insert(root,element);

    }
    private BinaryTreeNode<T> insert(BinaryTreeNode binaryTreeNode,T element) {
        if (binaryTreeNode == null) {
            binaryTreeNode = new BinaryTreeNode(element);
        } else if (element.compareTo((T) binaryTreeNode.element) < 0) {  //向左子树寻找插入位置
            binaryTreeNode.left = insert(binaryTreeNode.left, element);

            if (isLargerThanOne(binaryTreeNode) == false) {
                if (element.compareTo((T) binaryTreeNode.left.element) < 0) {
                    binaryTreeNode = singleLeftRotation(binaryTreeNode);
                } else {
                    binaryTreeNode = doubleLeftRightRotation(binaryTreeNode);
                }
            }
        } else if (element.compareTo((T) binaryTreeNode.element) > 0) {
            binaryTreeNode.right = insert(binaryTreeNode.right, element);
            if (isLargerThanOne(binaryTreeNode) == false) {
                if (element.compareTo((T) binaryTreeNode.right.element) < 0) {
                    binaryTreeNode = singleRightRotation(binaryTreeNode);
                } else {
                    binaryTreeNode = doubleRightLeftRotation(binaryTreeNode);
                }
            } else {
                binaryTreeNode.height = Math.max(Depth(binaryTreeNode.left), Depth(binaryTreeNode.right)) + 1;

            }
        }return binaryTreeNode;
    }

    private boolean isLargerThanOne(BinaryTreeNode binaryTreeNode) {
        if (Math.abs(Depth(binaryTreeNode.left) - Depth(binaryTreeNode.right)) > 1) {
            return false;
        }
        else {
            return true;
        }
    }






    public static void main(String[] args) {
        LinkedBinaryTree linkedBinaryTree = new LinkedBinaryTree();
        linkedBinaryTree.add(50);
        linkedBinaryTree.add(30);
        linkedBinaryTree.add(40);
        linkedBinaryTree.add(20);
        linkedBinaryTree.add(32);
        linkedBinaryTree.add(35);
        linkedBinaryTree.add(80);
        linkedBinaryTree.add(90);
        linkedBinaryTree.add(85);
        linkedBinaryTree.add(88);
        linkedBinaryTree.insert(9);
        linkedBinaryTree.insert(6);
        linkedBinaryTree.insert(5);
        linkedBinaryTree.insert(19);
        linkedBinaryTree.insert(45);



        System.out.println(linkedBinaryTree.printTree());



    }
}

